算法 - 0 排序实现

快速排序

时间复杂度：O(nlogn)，最差情况为O(n^2)

空间复杂度：O(1)，没有使用额外空间

稳定性：不稳定

# -*- coding:utf-8 -*-

# 一、算法导论实现
def quickSort(array, l, r):
    if l >= r:
        return
    mid = partition(array, l, r)
    quickSort(array, l, mid - 1)
    quickSort(array, mid + 1, r)

"""在划分partition的过程中排序，使用小区游标i+循环游标j，将比key小的值j与i在的位置交换，直至分区后交换r与i+1的值，返回i+1的中心位置。"""
def partition(array, l, r):
    # 1.选择主元
    key = array[r]
    # 2.找到小区，使用小区最后一个元素i，游标j
    i = l - 1
    j = l
    for j in range(l, r):
        # 2.1 j循环+1，找到小于key的元素时候，i后移动，并将找到的arr[j]与arr[i]换位置
        if array[j] < key:
            i += 1
            array[i], array[j] = array[j], array[i]
    # 3.游标j循环后，i为小区的最后一个元素，将r与i+1换位置，则分割完成
    array[i + 1], array[r] = array[r], array[i + 1]
    return i + 1

if __name__ == '__main__':
    nums = [6, 1, 2, 7, 9, 9, 3, 4, 5, 10, 8, -1]
    quickSort(nums, 0, len(nums) - 1)
    print nums

归并排序

时间复杂度：O(nlogn)，最好最优平均

空间复杂度：O(n)，每次归并的时候需要开辟临时空间 2倍数组长度的空间

稳定排序

# -*- coding:utf-8 -*-

def mergeSort(array):
    # 1.划分小于等于1，则返回自己
    if len(array) <= 1:
        return array
    # 2.大于1，继续划分为左右，mid为中位index。返回为merge排序后的结果。
    else:
        mid = len(array) / 2
        print mid
        left = mergeSort(array[:mid])
        right = mergeSort(array[mid:])
        # 返回排序后的left+right
        return merge(left, right)

"""在merge的过程中排序，输入为left，right数组，使用i、j循环俩数组，返回排序好的合并数组result。"""
def merge(left, right):
    # 1.临时存储空间
    result = []
    # 2.left的下标i，right的下标j
    i = 0
    j = 0
    # 2.循环left和right，将小的存入result，i或j+1，直至i、j有一个分完
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # 3.将未循环完的剩余left或right数组的数字直接与result连接
    result += left[i:]
    result += right[j:]
    # 4.返回merge结果
    return result

if __name__ == '__main__':
    array = [9, 6, 1, 2, 5, 0, 4]
    result = mergeSort(array)
    print result